<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var twoSum = function (numbers, target) {
        // 方法一：对象（）---时间：O（n）（）---空间：O（n）（对象空间）
        // const obj = {};
        // for (let i = 0; i < numbers.length; i++) {
        //   const temp = target - numbers[i];
        //   if (obj[temp] !== undefined) {
        //     return [obj[temp] + 1, i + 1];
        //   } else {
        //     obj[numbers[i]] = i;
        //   }
        // }

        // 方法二：暴力法（）---时间：O（n^2）（）---空间：O（0）（）
        // for(let i=0;i<numbers.length;i++){
        //   for(let j=i+1;j<numbers.length;j++){
        //     if(numbers[i]+numbers[j]===target){
        //       return [i+1,j+1]
        //     }
        //   }
        // }

        // 方法三：双指针（）---时间：O（n）（）---空间：O（1）（）
        // let left = 0;
        // let right = numbers.length - 1;
        // while (left < right) {
        //   if (numbers[left] + numbers[right] > target) {
        //     right--;
        //   }
        //   if (numbers[left] + numbers[right] < target) {
        //     left++;
        //   }
        //   if (numbers[left] + numbers[right] === target) {
        //     return [left + 1, right + 1];
        //   }
        // }

        // 方法四：二分查找（）---时间：O（nlogn）（）---空间：O（1）（）
        for (let i = 0; i < numbers.length; i++) {
          // 为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找
          let left = i + 1;
          let right = numbers.length - 1;
          while (left <= right) {
            const mid = (left + right) >> 1;
            const sum = numbers[i] + numbers[mid];
            if (sum > target) {
              right = mid - 1;
            } else if (sum < target) {
              left = mid + 1;
            } else {
              return [i + 1, mid + 1];
            }
          }
        }
      };
      console.log(twoSum([2, 7, 11, 15], 9));
      console.log(twoSum([2, 3, 4], 6));
      console.log(twoSum([5, 25, 75], 100));
    </script>
  </body>
</html>
